package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.ArrayList;

/*
{A, B, C}
	ABC
	ACB
	BAC
	BCA
	CAB
	CBA
	6个
 */
public class f全排列by递归and迭代 {
	public static void main(String[] args) {
		f全排列by递归and迭代 test = new f全排列by递归and迭代();
		ArrayList<String> res1 = test.getPermutation1("ABC");
		System.out.println(res1);
		String string = "123456";
		ArrayList<String> res2 = test.getPermutation2(string, string.length() - 1);
		System.out.println(res2);
	}
	
	/**
	 * 迭代形式
	 * "逐步生成法"
	 * @param s
	 * @return
	 */
	public ArrayList<String> getPermutation1(String s) {
		int length = s.length();//原串长度
		ArrayList<String> res = new ArrayList<String>();//“最终结果集合”
		res.add(s.charAt(0) + "");//初始存放第一个字符
		for (int i = 1; i < length; i++) {//开始迭代
			ArrayList<String> newRes = new ArrayList<String>();//定义“帮助集合”
			char current = s.charAt(i);//获取要插入的字符，从原串
			for (String element : res) {//对res中的每一个元素，进行“前插”，“后插”，“中间插”
				newRes.add(current + element);//前插
				newRes.add(element + current);//后插
				for (int j = 1; j < element.length(); j++) {//中间插;会跳过只有1个字符的res的元素
					newRes.add(element.substring(0, j) + current + element.substring(j));//通过截取字符串的方式实现中间插
				}
			}
			res = newRes;//覆盖
		}
		return res;
	}
	
	/**
	 * 递归形式
	 * @param s
	 * @param current
	 * @return
	 */
	public ArrayList<String> getPermutation2(String s, int current) {
		ArrayList<String> newRes = new ArrayList<String>();//“最终结果集合”
		if (current == 0) {
			newRes.add(s.charAt(current) + "");
			return newRes;
		}
		ArrayList<String> oldRes = getPermutation2(s, current - 1);
		char currentChar = s.charAt(current);
		for (String element : oldRes) {
			newRes.add(currentChar + element);
			newRes.add(element + currentChar);
			for (int i = 1; i < element.length(); i++) {
				newRes.add(element.substring(0, i) + currentChar + element.substring(i));
			}
		}
		return newRes;
	}
}
